package com.example.demo.algorithm.practice;

import java.util.ArrayList;
import java.util.BitSet;
import java.util.List;

/**
 * @author liweizhi
 * @date 2020/4/22 11:47
 */
public class FindTwoDeletedNumber {
    static int start = 1;
    static int count = 100_0000;

    public static void main(String[] args) {

        List<Integer> list = new ArrayList<>(count);
        for (int i = start; i <= count; i++) {
            list.add(i);
        }
        // 随机删除
        randomRemove(count, list);
        randomRemove(count, list);
        // 找出来
        findThem(list);

        findThem002(list);

    }

    private static void findThem(List<Integer> list) {
        long startTime = System.currentTimeMillis();
        BitSet bitSet = new BitSet(count);
        for (Integer integer : list) {
            bitSet.set(integer);
        }

        for (int i = start; i <= count; i++) {
            if (!bitSet.get(i)) {
                System.out.println("find:" + i);
            }
        }
        long endTime = System.currentTimeMillis();
        System.out.println("cust ms:" + (endTime - startTime));
    }

    private static void findThem002(List<Integer> list) {
        long startTime = System.currentTimeMillis();
        int a = 0, x1 = 0, x2 = 0;
        for (Integer integer : list) {
            a ^= integer;
        }
        for (int i = start; i <= count; i++) {
            a ^= i;
        }
        // now a = x1 ^ x2
        // 取a最右面的"1"
        int j = a & (~a + 1);
        for (Integer integer : list) {
            // 第j位是0
            if ((integer & j) == 0) {
                x1 ^= integer;
            }
        }
        for (int i = start; i <= count; i++) {
            if ((i & j) == 0) {
                x1 ^= i;
            }
        }
        // now x1 = x1
        x2 = a ^ x1;
        System.out.println("002 find : " + x1);
        System.out.println("002 find : " + x2);
        long endTime = System.currentTimeMillis();
        System.out.println("002 cust ms:" + (endTime - startTime));
    }

    private static void randomRemove(int count, List<Integer> list) {
        int index = (int) (Math.random() * count);
        System.out.println("delete " + list.remove(index));
    }
}
